package oj;

import java.util.HashMap;
import java.util.Map;

public class LC337 {
    public int rob(TreeNode root) {
        Map<TreeNode,Integer> map=new HashMap<>();
        return rob1(root,map);


    }
    private int rob1(TreeNode root,Map<TreeNode,Integer> map){
        if(root==null) return 0;
        if(map.containsKey(root)) return map.get(root);
        int money=root.val;
        if(root.left!=null){
            money+=rob1(root.left.left,map)+rob1(root.left.right,map);
        }
        if(root.right!=null){
            money+=rob1(root.right.left,map)+rob1(root.right.right,map);
        }

        int res=Math.max(money,rob1(root.left,map)+rob1(root.right,map));
        map.put(root,res);
        return res;
    }
}
